package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code38
 * @Description 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 * <p>
 * 为了让您更好地理解问题，以下面的二叉搜索树为例：
 * <p>
 * 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
 * <p>
 * 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-20 15:39
 */
public class Code38 {

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    Node head;
    Node tail;

    public  Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        traverse(root);
        head.left = tail;
        tail.right = head;
        return head;
    }

    public void traverse(Node root) {

        if (root != null) {
            traverse(root.left);
            if (head != null) {
                tail.right = root; // 如果头节点为空则说明没有到第一层
            } else {
                head = root;
            }
            root.left = tail;
            tail = root;
            traverse(root.right);
        }
    }
}
/*
二叉搜索树按从小到大排
中序遍历可以解决
中序遍历的递归操作时牢记
一定是按照从小到大的顺序依次访问每一个结点
比如当前访问的结点的上一个访问的结点一定是他的前驱
当前访问的结点的下一个结点一定是他的后继
所以只要设置两个变量，一个头节点一个尾结点
遍历的时候根据头节点和尾结点对链表进行链接
链接之后进行尾结点的更新
 */